In [1]:
"""
Modified from: http://hubpages.com/technology/Simplex-Algorithm-in-Python
"""

from __future__ import division
from numpy import *

# Ref: http://stackoverflow.com/questions/23344185/how-to-convert-a-decimal-number-into-fraction
from fractions import Fraction


class Tableau:
 
    def __init__(self, obj):
        self.obj = [1] + obj
        self.rows = []
        self.cons = []
        self.no_variables = len(obj)
        self.no_constraints = 0
        self.is_fraction = False # set True to output in fraction
 
    def add_constraint(self, expression, value):
        self.rows.append([0] + expression)
        self.cons.append(value)
        self.no_constraints += 1
        self.header_tableau = ["Basic"] + ["x"+str(i+1) for i in range(self.no_variables)] \
                                        + ["s"+str(i+1) for i in range(self.no_constraints)] \
                                        + ["Solution"]
                
        self.basic_variables = ["s"+str(i+1) for i in range(self.no_constraints)]
 
    def _pivot_column(self):
        low = 0
        idx = 0
        for i in range(1, len(self.obj)-1):
            if self.obj[i] < low:
                low = self.obj[i]
                idx = i
        if idx == 0: return -1
        return idx
 
    def _pivot_row(self, col):
        rhs = [self.rows[i][-1] for i in range(len(self.rows))]
        lhs = [self.rows[i][col] for i in range(len(self.rows))]
        ratio = []
        for i in range(len(rhs)):
            if lhs[i] == 0:
                ratio.append(99999999 * abs(max(rhs)))
                continue
            ratio.append(rhs[i]/lhs[i])
        return argmin(ratio)
 
    def display(self):   
        if self.is_fraction:
            # Formatting the output in fraction
            # Ref: https://pyformat.info/
            fmt = '{:<8}'.format("Basic") \
                  + "".join(['{:>8}'.format("x"+str(i+1)) for i in range(self.no_variables)])   \
                  + "".join(['{:>8}'.format("s"+str(i+1)) for i in range(self.no_constraints)]) \
                  + '{:>8}'.format("Sol.")

            fmt += "\n" 
            fmt += '{:<8}'.format("z") \
                   + "".join(["{:>8}".format(Fraction(item).limit_denominator(3)) for item in self.obj[1:]])

            for i, row in enumerate(self.rows):
                fmt += "\n" 
                fmt += '{:<8}'.format(self.basic_variables[i]) \
                       + "".join(["{:>8}".format(Fraction(item).limit_denominator(3)) for item in row[1:]])
            print fmt
            
        else:
            # Formatting the output in float with 2 decimal places
            fmt = '{:<8}'.format("Basic") \
                  + "".join(['{:>8}'.format("x"+str(i+1)) for i in range(self.no_variables)])   \
                  + "".join(['{:>8}'.format("s"+str(i+1)) for i in range(self.no_constraints)]) \
                  + '{:>8}'.format("Sol.")

            fmt += "\n" 
            fmt += '{:<8}'.format("z") + "".join(["{:>8.2f}".format(item) for item in self.obj[1:]])

            for i, row in enumerate(self.rows):
                fmt += "\n" 
                fmt += '{:<8}'.format(self.basic_variables[i]) \
                       + "".join(["{:>8.2f}".format(item) for item in row[1:]])
            print fmt            
              
#       print '\n', matrix([self.obj] + self.rows)
 
    def _pivot(self, row, col):
        e = self.rows[row][col]
        self.rows[row] /= e
        for r in range(len(self.rows)):
            if r == row: continue
            self.rows[r] = self.rows[r] - self.rows[r][col]*self.rows[row]
        self.obj = self.obj - self.obj[col]*self.rows[row]
 
    def _check(self):
        if min(self.obj[1:-1]) >= 0: return 1
        return 0
         
    def solve(self):
        # build full tableau
        for i in range(len(self.rows)):
            self.obj += [0]
            ident = [0 for r in range(len(self.rows))]
            ident[i] = 1
            self.rows[i] += ident + [self.cons[i]]
            self.rows[i] = array(self.rows[i], dtype=float)
        self.obj = array(self.obj + [0], dtype=float)
 
        # solve
        self.display()
        while not self._check():
            c = self._pivot_column()
            r = self._pivot_row(c)
            self._pivot(r,c)
            # print '\npivot column: %s\npivot row: %s'%(c+1,r+2)
            print '\n'
            print 'Entering Variable: ', self.header_tableau[c]
            print 'Leaving Variable : ', self.basic_variables[r]
            print '\n'
            # Updating the basic variable
            for index, item in enumerate(self.basic_variables):
                if self.basic_variables[index] == self.basic_variables[r]:
                    self.basic_variables[index] = self.header_tableau[c]
                               
            self.display()
             
if __name__ == '__main__':
 
    """
    max z = 2x + 3y + 2z
    st
    2x + y + z <= 4
    x + 2y + z <= 7
    z          <= 5
    x,y,z >= 0
    """
 
    t = Tableau([-2,-3,-2])
    t.add_constraint([2, 1, 1], 4)
    t.add_constraint([1, 2, 1], 7)
    t.add_constraint([0, 0, 1], 5)
    t.is_fraction = True
    t.solve()


Basic         x1      x2      x3      s1      s2      s3    Sol.
z             -2      -3      -2       0       0       0       0
s1             2       1       1       1       0       0       4
s2             1       2       1       0       1       0       7
s3             0       0       1       0       0       1       5


Entering Variable:  x2
Leaving Variable :  s2


Basic         x1      x2      x3      s1      s2      s3    Sol.
z           -1/2       0    -1/2       0     3/2       0    21/2
s1           3/2       0     1/2       1    -1/2       0     1/2
x2           1/2       1     1/2       0     1/2       0     7/2
s3             0       0       1       0       0       1       5


Entering Variable:  x1
Leaving Variable :  s1


Basic         x1      x2      x3      s1      s2      s3    Sol.
z              0       0    -1/3     1/3     4/3       0    32/3
x1             1       0     1/3     2/3    -1/3       0     1/3
x2             0       1     1/3    -1/3     2/3       0    10/3
s3             0       0       1       0       0       1       5


Entering Variable:  x3
Leaving Variable :  x1


Basic         x1      x2      x3      s1      s2      s3    Sol.
z              1       0       0       1       1       0      11
x3             3       0       1       2      -1       0       1
x2            -1       1       0      -1       1       0       3
s3            -3       0       0      -2       1       1       4

Solve the following problem: $$ \left.\begin{array}{rrcl} \max & 3x+2y+5z \\ \text {s.t.:} & & & \\ & x + 2y + z \leq 430 \text{ (Constraint 1)}\\ & 3x + 2z \leq 460 \text{ (Constraint 2)} \\ & x + 4y \leq 420 \text{ (Constraint 3)} \\ & x, y, z \geq 0 \text{ (Non-negativity)} \\ \end{array}\right\} $$


In [2]:
sm = Tableau([-3, -2, -5])
sm.add_constraint([1, 2, 1], 430)
sm.add_constraint([3, 0, 2], 460)
sm.add_constraint([1, 4, 0], 420)
sm.is_fraction = True
sm.solve()


Basic         x1      x2      x3      s1      s2      s3    Sol.
z             -3      -2      -5       0       0       0       0
s1             1       2       1       1       0       0     430
s2             3       0       2       0       1       0     460
s3             1       4       0       0       0       1     420


Entering Variable:  x3
Leaving Variable :  s2


Basic         x1      x2      x3      s1      s2      s3    Sol.
z            9/2      -2       0       0     5/2       0    1150
s1          -1/2       2       0       1    -1/2       0     200
x3           3/2       0       1       0     1/2       0     230
s3             1       4       0       0       0       1     420


Entering Variable:  x2
Leaving Variable :  s1


Basic         x1      x2      x3      s1      s2      s3    Sol.
z              4       0       0       1       2       0    1350
x2          -1/3       1       0     1/2    -1/3       0     100
x3           3/2       0       1       0     1/2       0     230
s3             2       0       0      -2       1       1      20

In [ ]: